'''
给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutations-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
'''
class Solution:
    def permuteUnique(self, nums):
        import copy
        import collections
        res = []
        midres = []
        numcount = collections.defaultdict(int)
        for j in nums:
            numcount[j]+=1
        def dfs(nums,index,midres):
            if len(midres) == len(nums) :
                if midres not in res:
                    kk = copy.deepcopy(midres)
                    res.append(kk)
                    return
            for laternode in nums[:index]+nums[index+1:]:
                if numcount[laternode]>0:
                    midres.append(laternode)
                    numcount[laternode]-=1
                    dfs(nums,nums.index(laternode),midres)
                    numcount[laternode]+=1
                    midres.pop()
        nums.sort()
        for  index in range(len(nums)):
            midres.append(nums[index])
            numcount[nums[index]] -= 1
            dfs(nums,index,midres)#从每一个节点出发，找出点连接的所有路径
            midres.pop()
            numcount[nums[index]] += 1
        print(res)


if __name__ == '__main__':
    s = Solution()
    nums = [1,-1,1,2,-1,2,2,-1]
    s.permuteUnique(nums)
